/*
 * FindAndUnion.cpp
 *
 *  Created on: Apr 4, 2014
 *      Author: zby
 */
#include <stdint.h>
//#include <libio.h>
#include <iostream>

#include "FindAndUnion.h"

using namespace std;
/*
* @brief    Constructor. Crate id table for find and union algorithm.
* @param    length table.
* @retval    none
*/
FindAndUnion::FindAndUnion(int len) : len(len)
{
    id = NULL;
    if(id == NULL) id = new int[len];
    if(id == NULL ) throw "memory limit";

    for(int i=0;i<len;i++)
        id[i]=i;
}

/*
* @brief    Copy constructor
* @param    FindAndUnion class to be copy
* @retval    none
*/
FindAndUnion::FindAndUnion(const FindAndUnion & fau) : len(fau.len)
{
    id = NULL;
    if(id == NULL) id = new int[this->len];
    if(id == NULL ) throw "memory limit";

    for(int i=0;i<len;i++)
        id[i]=fau.id[i];
}


FindAndUnion::~FindAndUnion()
{
    if(id != NULL) delete [] id;
    id = NULL;
}

/*
* @brief    Find root of given member
* @param    index of given member to find root
* @retval    none
*/
int FindAndUnion::root(int i)
{
    while(id[i]!=i) i=id[i];
    return i;
}

/*
* @brief    Merge to member
* @param    member1 to be merge.
* @param    member2 to be merge. It will be a root of this merge
* @retval    if false - means p and q have the same root and nothing have been done
*/
bool FindAndUnion::unite(int p, int q)
{
    int i=root(p);
    int j=root(q);
    if(i==j) return false;
    else id[i]=j;

    return true;
}

/*
* @brief    Check if given members have the same root
* @param    member1 to be merge.
* @param    member2 to be merge.
* @retval    true if have the same root.
*/
bool FindAndUnion::ifTheSameRoot(int p, int q)
{
    return root(p)==root(q);
}

